//如果字符串 s 中 不存在 两个不同字符 频次 相同的情况，就称 s 是 优质字符串 。 
//
// 给你一个字符串 s，返回使 s 成为 优质字符串 需要删除的 最小 字符数。 
//
// 字符串中字符的 频次 是该字符在字符串中的出现次数。例如，在字符串 "aab" 中，'a' 的频次是 2，而 'b' 的频次是 1 。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "aab"
//输出：0
//解释：s 已经是优质字符串。
// 
//
// 示例 2： 
//
// 
//输入：s = "aaabbbcc"
//输出：2
//解释：可以删除两个 'b' , 得到优质字符串 "aaabcc" 。
//另一种方式是删除一个 'b' 和一个 'c' ，得到优质字符串 "aaabbc" 。 
//
// 示例 3： 
//
// 
//输入：s = "ceabaacb"
//输出：2
//解释：可以删除两个 'c' 得到优质字符串 "eabaab" 。
//注意，只需要关注结果字符串中仍然存在的字符。（即，频次为 0 的字符会忽略不计。）
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 10⁵ 
// s 仅含小写英文字母 
// 
//
// Related Topics 贪心 字符串 排序 👍 49 👎 0


package leetcode.editor.cn;

import java.util.HashSet;
import java.util.Set;

/**
 * 字符频次唯一的最小删除次数
 * @date 2022-10-31 09:14:20
 */
class P1647_MinimumDeletionsToMakeCharacterFrequenciesUnique{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new P1647_MinimumDeletionsToMakeCharacterFrequenciesUnique().new Solution();
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int minDeletions(String s) {
		int[] a = new int[26];
		char[] chars = s.toCharArray();
		for (char c: chars) {
			a[c-'a']++;//统计字符串中各个字符出现的次数
		}

		Set<Integer> set = new HashSet<>();
		int res = 0;
		for (int i : a) {
			if(i != 0){  // 有数目才进行判断
				while (set.contains(i)){// set已经包含就自减
						i--;
						res++;
				}
				if(i!=0)
					set.add(i); // 自减到0时，表示完全删除了某个字母，不能加入set中
			}
		}
		return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
